算法概论实验八 贪心法

发表于 | 分类于 
1
2
3
4
5
6
7
8
9
10
实验八

实验目的与要求：
（1）	掌握贪心法的基本思想和设计方法。

1．区间调度问题
【问题描述】
给定n个活动，其中的每个活动ai包含一个起始时间si与结束时间fi。设计与实现算法从n个活动中找出一个最大的相互兼容的活动子集S。

要求：分别设计动态规划与贪心算法求解该问题。其中，对贪心算法分别给出递归与迭代两个版本的实现。

#贪心法迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include "stdafx.h"
#include <iostream>
using namespace std;


int GetSet(int *si, int *fi, int n)
{
	//创建一个记录数组，用于最后判定是否选取
	bool *result=new bool[n];
	memset(result, false, sizeof(result));

	result[0] = true;//初始设定
	int selected_index = 0;//第一个选中的
	for (int i = 1; i < n;i++)
	{
		if (fi[selected_index] <= si[i])//这种情况下是能够兼容的
		{
			result[i] = true;
			selected_index = i;
		}
	}

	//输出
	int nct = 0;
	cout << "最大兼容子集为：";
	for (int i = 0; i < n;i++)
	{
		if (result[i]==true)
		{
			cout << i + 1 << "\t";
			nct++;
		}
	}
	return nct;
}

int main()
{
	int si[] = {1,3,0,5,3,5,6,8,8,2,12};
	int fi[] = {4,5,6,7,8,9,10,11,12,13,14};
	int n = 11;
	cout << endl<<"省去排序过程,最兼容活动子集的数目为："<< GetSet(si, fi, n);
	return 0;
}

#贪心法 递归
每次递归，将问题的规模减少1~n，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include "stdafx.h"
#include <iostream>
using namespace std;

//i是上一个符合条件的id，为了完整性，在第一列加上-1，n是总数目
void GetSet(int *si, int *fi, int i, int n)
{
	int m = i + 1;
	while (m <= n && si[m] < fi[i])//找第一个符合的
		m = m + 1;
	if (m <= n)
	{
		cout << m << "\t";
		GetSet(si, fi, m, n);
	}
}

int main()
{
	int si[] = { -1,1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12 };
	int fi[] = { -1,4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
	int n = 11;
	GetSet(si, fi, 0, 11);
}

#动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
using namespace std;

//动态规划实现
int GetSet(int *start, int *finish, int n)
{
	//c[i][j]表示第i个工作结束后到第j个工作开始前之间存在的可兼容的工作个数
	//new c[i][j]
	int **c = new int *[n];
	for(int i=0; i<n; i++)
		c[i] = new int[n];

	//c[i][j]初始赋值
	for(i=0; i<n; i++)
		for(int j=0; j<n; j++)
			c[i][j] = 0;

	for(int j=0; j<n; j++)
	{
		for(i=0; i<n; i++)
		{
			if(i<j)
			{
				int s = finish[i];
				int f = start[j];
				for(int k=i+1; k<j; k++)
					if(start[k]>=s && finish[k]<=f)
					{
						if(c[i][j]<(c[i][k]+c[k][j]+1))
							c[i][j] = c[i][k]+c[k][j]+1; //分解成更小子问题
					}						
			}
		}			
	}
	return c[0][n-1];	//最终目标
}

int main()
{
	//已经按完成时间排好序
	int start[] = {-1,3,0,5,3,5,6,8,8,2,1000};
	int finish[] = {0,5,6,7,8,9,10,11,12,13,10000};
    int n = 11;	//活动只有9个
    cout<<"最大兼容活动子集的大小为："<<GetSet(start, finish, n)<<endl;
	return 0;
}